package leetcode.code1631;

import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int[] d = new int[] { 0, -1, 0, 1, -1, 0, 1, 0 };
	int m, n;
	boolean[][] been;
	PriorityQueue<int[]> queue;
	int[][] heights;

	public int minimumEffortPath(int[][] heights) {
		m = heights.length;
		n = heights[0].length;
		if (m == 1 && n == 1) {
			return 0;
		}
		this.heights = heights;
		been = new boolean[m][n];
		been[0][0] = true;
		// 移动到(x,y)当前答案，x，y
		queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
		init(0, 0, 0);
		int ans = Integer.MAX_VALUE;
		while (!queue.isEmpty()) {
			int[] next = queue.poll();
			if (next[1] == m - 1 && next[2] == n - 1) {
				ans = Math.min(ans, next[0]);
			} else
				init(next[1], next[2], next[0]);
		}
		return ans;
	}

	public void init(int x, int y, int max) {
		been[x][y] = true;
		for (int i = 0; i < 8; i += 2) {
			int nextx = x + d[i], nexty = y + d[i + 1];
			int h = this.heights[x][y];
			if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n && !been[nextx][nexty]) {
				int nh = this.heights[nextx][nexty];
				queue.add(new int[] { Math.max(Math.abs(nh - h), max), nextx, nexty });
			}
		}
	}

	@Override
	public void debug4() {
		H.compare(2, this.minimumEffortPath(H.str2array1("[[1,2,2],[3,8,2],[5,3,5]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
